package listbyorder.access001_100.test32;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/5/30 10:23
 */
public class Solution1 {

    // 动态规划（自己的方法）
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        int ans = 0;
        char[] chars = s.toCharArray();
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == ')') {
                if (chars[i - 1] == '(') {
                    dp[i] = i - 1 > 0 ? dp[i - 2] + 2 : 2;
                } else {
                    int pre = i - dp[i - 1] - 1;
                    if (pre >= 0 && chars[pre] == '(') {
                        dp[i] = pre > 0 ? dp[pre - 1] + dp[i - 1] + 2 : dp[i - 1] + 2;
                    }
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
